from typing import List


class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        if m == 1:
            return sum(nums)

        size = len(nums)

        # dp[i][j] 前j个字符分为i个子数组的最小最大值
        dp = [[0] * len(nums) for _ in range(m)]

        # dp[0]可以当做前缀和使用
        dp[0][0] = nums[0]
        for j in range(1, size):
            dp[0][j] = dp[0][j - 1] + nums[j]

        for i in range(1, m):
            j1 = i - 1
            for j2 in range(i, size):
                dp[i][j2] = max(dp[i - 1][j1], dp[0][j2] - dp[0][j1])
                while dp[i - 1][j1 + 1] <= dp[0][j2] - dp[0][j1]:
                    j1 += 1
                    dp[i][j2] = min(dp[i][j2], max(dp[i - 1][j1], dp[0][j2] - dp[0][j1]))

        # for row in dp:
        #     print(row)

        return dp[-1][-1]


if __name__ == "__main__":
    print(Solution().splitArray([7, 2, 5, 10, 8], 2))  # 18
    print(Solution().splitArray([1, 2, 3, 4, 5], 2))  # 9
    print(Solution().splitArray([1, 4, 4], 3))  # 4

    # 测试用例28
    print(Solution().splitArray([7, 6, 5, 4, 3, 2, 1], 2))  # 15

    # 测试用例29
    print(Solution().splitArray([0, 8, 1, 4], 4))  # 8
